import java.util.Arrays;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Home-pc
 * Date: 2023-08-26
 * Time: 12:04
 */
public class Sort {
    @Override
    public String toString() {
        return "Sort{}";
    }

    public static void insertSort(int[] array ){
            for (int i =1; i < array.length; i++) {
                int temp=array[i];//记录当前的元素，准备随时插入，同时放置元素被覆盖掉
                int j=i-1;
                for (; j>=0; j--) {
                    if(array[j]>temp){
                        //当前j下标的元素后移
                        array[j+1]=array[j];
                    }else{
                        break;
                    }
                }
                array[j+1]=temp;//没有j下标的元素大，插入它的后面
            }
        }

        //
    public  static  void shell(int[] array,int gap){
        for (int i =gap; i < array.length; i++) {//这里的i++，可以针对每一个分组
            int temp=array[i];//记录当前的元素，准备随时插入，同时放置元素被覆盖掉
            int j=i-gap;
            for (; j>=0; j-=gap) {
                if(array[j]>temp){
                    //当前j下标的元素后移
                    array[j+gap]=array[j];
                }else{
                    break;
                }
            }
            array[j+gap]=temp;//没有j下标的元素大，插入它的后面
        }
    }
    public static void shellSort(int[] array){
            int gap=array.length;
            while(gap>1){
                gap/=2;
                shell(array,gap);//这里在最后一定会进行一次gap=1的插入排序
            }
    }

    //
    public static void selectSort(int[] array){
        for(int i=0;i< array.length;i++){
            int minIndex=i;
            for (int j = i+1; j < array.length; j++) {
                if(array[j]<array[minIndex]){
                    minIndex=j;
                }
            }
            swap(array,i,minIndex);
        }
    }
    private static void swap(int[] array,int i,int j){
        int temp=array[i];
        array[i]=array[j];
        array[j]=temp;
    }

    //
    public static void selectSort2(int[] array){
        int left=0;
        int right= array.length-1;
        while(left<right){
            int minIndex=left;
            int maxIndex=left;
            for (int i = left+1; i <=right; i++) {
                if(array[i]<array[minIndex]){
                    minIndex=i;
                }
                if(array[i]>array[maxIndex]){
                    maxIndex=i;
                }
            }
            swap(array,minIndex,left);
            if(left==maxIndex){
                maxIndex=minIndex;
            }
            swap(array,maxIndex,right);

            left++;
            right--;
        }
    }

    //
    public static void heapSort(int[] array){
        createBigHeap(array);
        int end= array.length-1;
        while(end>0){
            swap(array,end,0);
            shiftDown(array,0,end);
            end--;
        }
    }
    private static void createBigHeap(int[] array){
        for (int i = (array.length-1-1)/2; i>=0; i--) {
            shiftDown(array,i, array.length);
        }
    }
    private static void shiftDown(int[] array,int parent,int len){
        int child=parent*2+1;
        while(child<len){
            if(child+1<len && array[child]<array[child+1]){
                child=child+1;
            }
            if(array[child]>array[parent]){
                swap(array,child,parent);
                parent=child;
                child=parent*2+1;
            }else{
                break;
            }
        }
    }

    //
    public  static  void bubbleSort(int[] arrary){
        for (int i = 0; i < arrary.length-1; i++) {
            boolean flag=false;
            for (int j = 0; j < arrary.length-1-i; j++) {
                if(arrary[j]>arrary[j+1]){
                    swap(arrary,j,j+1);
                    flag=true;
                }
            }
            if(!flag){
                break;
            }
        }
    }


    //
    public static void quickSort(int[] array){
        quick(array,0,array.length-1);
    }
    private static void quick(int[] array,int start,int end){
        if(start>=end){
            return;
        }
        //直接插入排序优化
        if(end-start+1<=10){
            insertSortForQuick(array,start,end);
            return;
        }
        //三数取中优化
        int mid=threeNum(array,start,end);
        swap(array,mid,start);

        int pivot=parttion(array,start,end);//求出基准值，依次为中间值划分序列
        quick(array,start,pivot-1);//左数
        quick(array,pivot+1,end);//右数
    }
    public static void insertSortForQuick(int[] array,int left,int right ){
        for (int i =left+1; i <=right; i++) {
            int temp=array[i];//记录当前的元素，准备随时插入，同时放置元素被覆盖掉
            int j=i-1;
            for (; j>=left; j--) {
                if(array[j]>temp){
                    //当前j下标的元素后移
                    array[j+1]=array[j];
                }else{
                    break;
                }
            }
            array[j+1]=temp;//没有j下标的元素大，插入它的后面
        }
    }

    private static int parttion1(int[] array,int left,int right){
        int i=left;
        int temp=array[left];//拿这个值和其它元素比较
        while(left<right){
            while(left<right && array[right]>=temp){//找到右边第一个比temp小的值
                right--;
            }
            while(left<right && array[left]<=temp){//找到左边第一个比temp大的值
                left++;
            }
            swap(array,left,right);//交换这两个值
        }

        swap(array,left,i);//交换某个中间值和temp的值，使得temp为真正的中间值
        return left;//返回这个中间位置的下标
    }

    //
    private static int parttion(int[] array,int left,int right){
        int temp=array[left];
        while(left<right){
            while(left<right && array[right]>=temp){
                right--;
            }
            array[left]=array[right];
            while(left<right && array[left]<=temp){
                left++;
            }
            array[right]=array[left];
        }
        array[right]=temp;
        return left;
    }

    //优化：三数取中
    private static int threeNum(int[] array,int left,int right){
        int mid=(left+right)/2;
        if(array[left]<array[right]){
            if(array[mid]<array[left]){
                return left;
            }else if(array[mid]>array[right]){
                return right;
            }else{
                return mid;
            }
        }else{
            if(array[mid]<array[right]){
                return right;
            }else if(array[mid]>array[left]){
                return  left;
            }else{
                return mid;
            }
        }
    }

    //非递归实现
    public static void quickSortByStack(int[] array){
        Stack<Integer> stack=new Stack<>();
        stack.push(array.length-1);//这里先push的右边，后push的左边
        stack.push(0);

        while(!stack.empty()){
            int left=stack.pop();
            int right=stack.pop();
            if(left>=right){//成立，说明该区间排序结束
                continue;
            }
            int index=parttion(array,left,right);
            stack.push(right);
            stack.push(index+1);

            stack.push(index-1);
            stack.push(left);
        }
    }

    //归并
    private static void merge(int[] array,int left,int mid,int right){
        //两个有序组合并为一个有序组
        int s1=left;
        int e1=mid;
        int s2=mid+1;
        int e2=right;//看似拆分为了两组，实际是一直在一个数组中进行的操作
        int[] tmpArr=new int[right-left+1];//用于存放合并后的数组

        int k=0;
        while(s1<=e1&&s2<=e2){//
            if(array[s1]<=array[s2]){//将s1放入数组中
                tmpArr[k++]=array[s1++];
            }else{
                tmpArr[k++]=array[s2++];
            }
        }
        while(s1<=e1){
            tmpArr[k++]=array[s1++];
        }
        while(s2<=e2){
            tmpArr[k++]=array[s2++];
        }
        for (int i = 0; i <k; i++) {
            array[i+left]=tmpArr[i];//tmpArr数组的首元素的下标不一定为0，但一定为left
        }
    }
    private static void mergeSortFunc(int[] array,int left,int right){
        if(left>=right){//最小拆分组的数量为1
            return;
        }
        int mid=(left+right)/2;
        mergeSortFunc(array,left,mid);
        mergeSortFunc(array,mid+1,right);//递归拆分至最小组，准备排序后合并
        merge(array,left,mid,right);
    }
    public static void mergeSort1(int[] array){
        mergeSortFunc(array,0,array.length-1);
    }

    //非递归归并
    public static void mergeSort(int[] array){
        int gap=1;
        while(gap<array.length){
            for (int i = 0; i <array.length; i+=gap*2) {
                int left=i;
                int mid=left+gap-1;
                int right=mid+gap;
                //mid和right可能越界，这里我们将其归置到一个数组中
                if(mid>=array.length){
                    mid=array.length-1;
                }
                if(right>=array.length){
                    right=array.length-1;
                }
                merge(array,left,mid,right);
            }
            gap*=2;
        }
    }

    //计数排序
    public static void countArray(int[] array){
        int maxVal=array[0];
        int minVal=array[0];
        for (int i = 0; i <array.length; i++) {//找到数组里的最大值和最小值
            if(array[i]<minVal){
                minVal=array[i];
            }
            if(array[i]>maxVal){
                maxVal=array[i];
            }
        }
        //建立一个计数的数组
        int range=maxVal-minVal+1;
        int[] count=new int[range];
        //遍历数组，做计数统计
        for (int i = 0; i <array.length; i++) {
            int val=array[i];
            count[val-minVal]++;
        }
        //遍历计数数组，并重写array数组的元素
        int index=0;
        for (int i = 0; i < count.length; i++) {
            int val=count[i];
            while(val!=0){
                array[index++]=i+minVal;
                val--;
            }
        }
    }
}
